package leetcode.editor.cn.dp;

// 0-1 Bag

/**
 * 先是找物体，再寻找合适的空间
 */
public class Bag01 {
// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
    public static int knapsackImplBy2DArray(int W, int N, int[] weights, int[] values) {
        int[][] dp = new int[N + 1][W + 1]; // dp[i][j]表示 i个物体 体积不超过j的集合的总价值
        for (int i = 1; i < N + 1; i++) {
            int w = weights[i - 1], v = values[i - 1];
            for (int j = 1; j < W + 1; j++) { // 排查体积
                if (j < w) {  // 不超过j， 放入w后超出体积
                    dp[i][j] = dp[i - 1][j]; // 当前不能放入i
                } else {
                    // 不放入w dp[i - 1][j]；  放入 dp[i - 1][j - w] + v
                    dp[i][j] = Math.max(dp[i - 1][j - w] + v, dp[i - 1][j]);
                }
            }
        }
        return dp[N][W];
    }

    public static int knapsackImplBy1DArray(int W, int N, int[] weights, int[] values) {
        int[] dp = new int[W + 1];
        for (int i = 1; i < N + 1; i++) {
            int w = weights[i - 1], v = values[i - 1];
            // 注意需要倒序，从后往前 防止dp[i -1]被覆盖
            for (int j = W; j > 0; j--) {
                if (j >= w) {
                    dp[j] = Math.max(dp[j], dp[j - w] + v);
                }
            }
            // 正序，第一轮循环 dp[j]必然为0， dp[j]会一直增加
//            for (int j = 0; j < W + 1; j++) {
//                if (j >= w) {
//                    dp[j] = Math.max(dp[j], dp[j - w] + v);
//                }
//            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 2};
        int[] values = {15, 20, 30, 10};
        knapsackImplBy1DArray(6, 4, weights, values);
    }


//    public static int knapsack(int W, int N, int[] weights, int[] values) {
//        int[][] dp = new int[N + 1][W + 1];
//        for (int i = 1; i <= N; i++) {
//            int w = weights[i - 1], v = values[i - 1];
//            for (int j = 1; j <= W; j++) {
//                if (j >= w) {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
//                } else {
//                    dp[i][j] = dp[i - 1][j];
//                }
//            }
//        }
//        return dp[N][W];
//    }
}
